package Algorithms.classic;

/**
 * description: 归并排序算法实现<br>
 * createTime: 2018/11/617:01 <br>
 *
 * @author zzh
 */
public class MergeSortTest {

    public static void main(String[] args) {
        SortUtils.test(MergeSortTest::mergeSort);
    }


    private static int[] mergeSort(int[] array) {
        int[] temp = new int[array.length];
        mergeSort(array, temp, 0, array.length - 1);
        return array;
    }


    private static void mergeSort(int[] array, int[] temp, int left, int right) {
        if(right <= left) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(array, temp, left, mid);
        mergeSort(array, temp, mid + 1, right);
        merge(array, temp, left, mid + 1, right);
    }


    private static void merge(int[] array, int[] temp, int left, int mid, int right) {
        int leftIndex = left;
        int index = left;
        int rightIndex = mid;
        while(leftIndex < mid && rightIndex <= right) {
            if(array[leftIndex] < array[rightIndex]) {
                temp[index++] = array[leftIndex++];
            } else {
                temp[index++] = array[rightIndex++];
            }
        }
        if(leftIndex == mid) {
            while(rightIndex <= right) {
                temp[index++] = array[rightIndex++];
            }
        } else {
            while(leftIndex < mid) {
                temp[index++] = array[leftIndex++];
            }
        }
        for (int i = left; i <= right; i++) {
            array[i] = temp[i];
        }
    }
}
